const largestRectangleArea = function(heights) {
    if(!Array.isArray(heights)) return false;
    if(!heights.length) return false;
    heights  = [0, ...heights, 0];
    let maxArea = 0;
    let start = 0;
    for(let i = 1; i < heights.length; i++){
        if(heights[i] >= heights[i - 1]){
            continue;
        }else{
            for(let j = i-1; j >= start; j--){
                let area = heights[j] * (i - j);
                console.log(heights[j], i, j, area);
                maxArea = Math.max(area,maxArea);
            }
            start = i;
        }
    }
    return maxArea;
};

const subarraySum = function(nums, k) {
    let res = [];
    nums = nums.sort((a,b) => a - b);
    const dfs = function(curPath,startIndex){
        if(startIndex === nums.length){
            res.push(curPath.slice());
            return;
        }
        curPath.push(nums[startIndex]);
        dfs(curPath,startIndex + 1);
        curPath.pop();
        dfs(curPath,startIndex + 1);
    }
    dfs([],0,k);
    console.log(res);
    return res.length;
};

const subarraySum2 = function(nums, k) {
    let res = [];
    nums = nums.sort((a,b) => a - b);
    const dfs = function(curPath,startIndex,rest){
        if(curPath.length && rest === 0){
            res.push(curPath.slice());
            return;
        }else if(rest < 0 || startIndex >= nums.length){
            return;
        }
        curPath.push(nums[startIndex]);
        dfs(curPath,startIndex + 1, rest - nums[startIndex]);
        curPath.pop();
        dfs(curPath,startIndex + 1, rest);
    }
    dfs([],0,k);
    return res.length;
};

// 最小子数组和问题
const sumSubarrayMins = function(arr) {
    let maxSum = 0;
    let stack = [];
    arr = [0,...arr, 0];
    const stackTopIndex = () => stack[stack.length - 1];
    stack.push(0); // 首位最小元素
    for(let i=1;i<arr.length;i++){
        if(arr[i] < arr[stackTopIndex()]){
            while(arr[i] < arr[stackTopIndex()]){
                let topItem = arr[stackTopIndex()];
                let topIndex = stack.pop();
                let nextItemNum = i - topIndex - 1;
                let preItemNum = topIndex - stackTopIndex() - 1;
                let sum = (nextItemNum + 1) * (preItemNum + 1) * topItem;
                maxSum += sum;
            }
        }
        stack.push(i);
    }
    return maxSum;
};

const reorganizeString = function(s) {
    let len = s.length;
    if(len < 2) return s;
    let used = new Set();
    let res = [];
    const dfs = function(curPath, used){
        if(curPath.length === len){
            res.push(curPath.slice());
            return;
        }

        for(let i = 0; i < len; i++){
            if(used.has(i)) continue;
            if(curPath.length && s[i] === curPath[curPath.length - 1]){
                continue
            }else{
                used.add(i);
                curPath.push(s[i]);
                dfs(curPath,used);
                used.delete(i);
                curPath.pop();
            }
        }
    }
    dfs([], used);
    if(res.length){
        return res.pop().join("");
    }else{
        return "";
    }
};

const repeatedSubstringPattern = function(s) {
    if(s.length < 2) return true;
    let len = s.length;
    let mid = Math.floor(len / 2);
    let result = false;
    for(let i= 0; i < mid; i++){
        let cmpStr =  s.substring(i+1) + s.substring(0, i+1);
        if(cmpStr == s){
            result = true;
            break;
        }else{
            continue;
        }
    }
    return result;
};

const distance = (arr) => arr[0] * arr[0] + arr[1] * arr[1];
const kClosest = function(points, k) {
    if(points.length <= k){
        return points;
    }
    let left = 0;
    let right = points.length - 1;
    while(left <= right){
        let pivotIndex = left;
        let pivotItem = distance(points[left]);
        [points[pivotIndex], points[right]] = [points[right],points[pivotIndex]];
        for(let i = left; i < right; i++){
            if(distance(points[i]) <= pivotItem){
                [points[pivotIndex],points[i]] = [ points[i],points[pivotIndex]]
                pivotIndex++;
            }
        }
        [points[pivotIndex],points[right]] = [ points[right],points[pivotIndex]]
        if(pivotIndex === k - 1){
            return points.slice(0,k);
        }else if(pivotIndex < k - 1){
            left  = pivotIndex + 1;
        }else{
            right = pivotIndex - 1;
        }
    }
    return null;
};

const findNumberOfLIS = function(nums) {
    let maxLen = 0; let ans = 0; let len = nums.length;
    let dp = new Array(len).fill(1);
    let cnt = new Array(len).fill(1);
    for(let i=0; i<len; i++){
        for(let j=0; j<i;j++){
            if(nums[i] > nums[j]){
                if(dp[j] + 1 > dp[i]){
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j];
                }else if(dp[j] + 1 === dp[i]){
                    cnt[i] += cnt[j];
                }
            }
        }
        if(dp[i] > maxLen){
            maxLen = dp[i];
            ans = cnt[i];
        }else if(dp[i] === maxLen){
            ans += cnt[i];
        }
    }

    return ans;
};

const getMaxMatrix = function(matrix) {
    let rows = matrix.length;
    let cols = matrix[0].length;
    let maxSum = -Infinity;
    let ans = new Array(4).fill(0);
    let bucket = new Array(cols).fill(0);
    debugger
    for(let i = 0; i < rows; i++){
        bucket.fill(0);
        for(let rowStart = i; rowStart < rows; rowStart++){
            let sum = -Infinity;
            let startColIndex = 0;
            for(let col = 0; col < cols; col++){
                bucket[col] += matrix[rowStart][col];
                if(sum > 0){
                    sum += bucket[col];
                }else{
                    sum = bucket[col];
                    startColIndex = col;
                }
                if(sum > maxSum){
                    maxSum = sum;
                    ans[0] = i;
                    ans[1] = startColIndex;
                    ans[2] = rowStart;
                    ans[3] = col;
                }
            }
        }
    }
    return ans;
};

const deleteAndEarn = function(nums) {
    let len = nums.length;
    if(len === 1) return nums[0];
    let map = new Map();
    for(let i = 0; i < len; i++){
        if(map.has(nums[i])){
            map.set(nums[i], map.get(nums[i]) + 1);
        }else{
            map.set(nums[i], 1);
        }
    }
    nums = Array.from(new Set(nums.sort((a,b) => a - b)));
    len = nums.length;
    let dp = new Array(len + 1).fill(0);
    dp[1] = nums[0] * map.get(nums[0]);
    for(let i=1; i<=len; i++){
        if(nums[i-1] - 1 === nums[i-2]){
            dp[i] = Math.max(dp[i-2] + nums[i-1] * map.get(nums[i-1]), dp[i-1]);
        }else{
            dp[i] = dp[i-1] + nums[i-1]*map.get(nums[i-1]);
        }
    }
    return dp[len];
};


const calculate = function(slices){
    let n = slices.length;
    let choose = (n + 1) / 3;
    let dp = new Array(n + 1).fill(0);
    dp = dp.map(item => new Array(choose + 1).fill(0));
    for(let i = 1; i <= n; i++){
        for(let j = 1; j <= choose; j++){
            dp[i][j] = Math.max(dp[i - 1][j], (i - 2 >= 0 ? dp[i - 2][j - 1] : 0) + slices[i - 1]);
        }
    }
    return dp[n][choose];
}

const maxSizeSlices = function(slices) {
    let slices1 = slices.slice(1);
    let slices2 = slices.slice(0,-1);
    let ans1 = calculate(slices1);
    let ans2 = calculate(slices2);
    return Math.max(ans1,ans2);
};



const lenLongestFibSubseq = function(arr) {
    let N = arr.length;
    let index = new Map();
    for(let i = 0; i<N;++i){
        index.set(arr[i], i);
    }
    let longest = new Map();
    let ans = 0;
    for(let k=0;k<N;++k){
        for(let j=0; j<k; ++j){
            let i = (index.get(arr[k] - arr[j])) !== undefined ? (index.get(arr[k] - arr[j])) : -1;
            if(i >= 0 && i < j){
                let cand = (longest.get(i * N + j) || 2) + 1;
                console.log(k, ":", j, ":", cand);
                longest.set(j * N + k, cand);
                ans = Math.max(ans,cand);
            }
        }
    }
    return ans >= 3 ? ans : 0;
};

const longestArithSeqLength = function(nums) {
    let N = nums.length;
    let dp = new Array(N).fill(0);
    dp = dp.map(item => new Array(1010).fill(0));
    let ans = 0;
    for(let k=0; k<N;++k){
        for(let j=0;j<k;++j){
            let d = nums[k] - nums[j] + 500;
            dp[k][d] = Math.max(dp[k][d], dp[j][d] + 1);
            ans = Math.max(ans, dp[k][d]);
        }
    }
    return ans;
};

const largestDivisibleSubset = function(nums) {
    let N = nums.length;
    let maxLen = 0;
    let ans = [];
    let dp = new Array(N).fill(0);
    let path = new Array(N).fill(0)
    dp[0] = 1;
    path[0] = [nums[0]];
    for(let k = 0; k < N; ++k){
        path[k] = [nums[k]];
        for(let j=0; j<k; ++j){
            if(nums[k] % nums[j] === 0){
                if(dp[j] + 1 > dp[k]){
                    dp[k] = dp[j] + 1;
                    path[k] = [...path[j],nums[k]];
                }
            }

        }
        if(dp[k] >= maxLen){
            maxLen = dp[k];
            ans = path[k]
        }
    }
    return ans;
};

// const longestValidParentheses = function(s) {
//     let len = s.length;
//     if(len < 2) return 0;
//     let result = 0;
//     const dfs = (curPath, left, right, startIndex) => {
//         if(startIndex === len && left === right){
//             result = Math.max(result,curPath.length);
//             return;
//         }
//         if(startIndex > len){
//             return;
//         }
//         if(left > Math.floor(len / 2)){
//             return;
//         }
//         if(s[startIndex] === '(' && left < Math.floor(len / 2)){
//             curPath.push(s[startIndex]);
//             dfs(curPath,left+1,right,startIndex + 1);
//             curPath.pop();
//             dfs(curPath,left,right,startIndex + 1);
//         }else if(s[startIndex] === ')' && right < left){
//             curPath.push(s[startIndex]);
//             dfs(curPath,left,right+1,startIndex + 1);
//             curPath.pop();
//             dfs(curPath,left,right,startIndex + 1);
//         }else{
//             dfs(curPath,left,right,startIndex + 1);
//         }
//     }
//     dfs([],0,0,0);
//     return result;
// };

const longestValidParentheses = function(s) {
    let len = s.length;
    if(len < 1) return 0;
    let ans;
    let dp = new Array(len).fill(0);
    dp[0] = 0;
    ans = dp[1] = s[0] === '(' && s[1] === ')' ? 2 : 0;
    if(len === 2){
        return dp[1];
    }
    for(let i=2; i<len; ++i){
        if(s[i] === '('){
            dp[i] = 0;
        }else if(i - dp[i - 1] - 2 >= 0){
            dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2];
        }
        ans = Math.max(ans,dp[i]);
    }
    return ans;
};

// 路由器覆盖问题
const computeScope = function(arr1, arr2, arr3){
    let ans = 0;
    for(let routerIndex = 0; routerIndex < arr2.length; routerIndex++){
        let range = arr3[routerIndex] -1;
        for(let i=0;i<=range;++i){
            if((routerIndex - 1 - i) >=0 && arr1[routerIndex - 1 - i] > 0){
                arr1[routerIndex - 1 - i] -= 1;
                if(arr1[routerIndex - 1 - i] === 0){
                    ans+=1;
                }
            }
            if((routerIndex - 1 + i) <arr1.length && arr1[routerIndex - 1 + i] > 0){
                arr1[routerIndex - 1 + i] -= 1;
                if(arr1[routerIndex - 1 + i] === 0){
                    ans+=1;
                }
            }
        }
    }
    return ans;
}

const splitArray = function(nums, m) {
    let N = nums.length;
    let dp = new Array(N + 1).fill(0).map(() => new Array(m + 1).fill(Infinity));
    let sub = new Array(N + 1).fill(0);
    for(let i = 0; i<N;++i){
        sub[i+1] = sub[i] + nums[i];
    }
    dp[0][0] = 0;
    for (let i = 1; i <= N; i++) {
        for (let j = 1; j <= Math.min(i, m); j++) {
            for (let k = 0; k < i; k++) {
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sub[i] - sub[k]));
            }
        }
    }
    return dp[N][m];
};

// 三数之和最接近的目标数
const threeSumClosest = function(nums, target) {
    nums = nums.sort((a,b) => a - b);
    let len = nums.length;
    let ans = Infinity;
    for(let i = 0; i < len - 2; ++i){
        let left = i + 1;
        let right = len - 1;
        while(left < right){
            let sum = nums[i] + nums[left] + nums[right];
            if(sum === target){
                return target;
            }
            if(Math.abs(target - sum) < Math.abs(target - ans)){
                ans = sum;
            }
            if(sum < target){
                left++
            }else{
                right--
            }
        }
    }
    return ans;
};

const removeElement = function(nums, val) {
    let len = nums.length;
    let i = 0;
    let j = 0;
    while(j < len){
        if(nums[j] !== val){
            nums[i] = nums[j];
            i++;
        }
        j++;
    }
    return i;
};

const moveZeroes = function(nums) {
    let len = nums;
    if(len < 2) return nums;
    let i = 0;
    let j = 1;
    while(j < len){
        if(nums[i] !== 0){
            i++;
        }
        if(nums[i] === 0 && nums[j] !== 0){
            [nums[i],nums[j]] = [nums[j], nums[i]];
            i++;
        }
        j++;
    }
    return nums;
};

const maxSatisfied = function(customers, grumpy, minutes) {
    let len = customers.length;
    let customerSum = new Array(len + 1).fill(0);
    for(let i = 1; i <= len; ++i){
        customerSum[i]  = customerSum[i-1] + customers[i-1];
    }
    let realSum = new Array(len + 1).fill(0);
    for(let j = 1; j <= len; ++j){
        if(grumpy[j-1] === 0){
            realSum[j] = realSum[j-1] + customers[j-1];
        }else{
            realSum[j] = realSum[j-1];
        }
    }
    let ans = 0;
    for(let m=minutes; m<=len; ++m){
        let sum = customerSum[m] - customerSum[m-minutes] + realSum[len] - realSum[m];
        ans = Math.max(ans,sum);
    }
    return ans;
};

const minWindow = function(s, t) {
    let len = s.length;
    if(len < t.length){
        return "";
    }
    let map = new Map();
    for(let i = 0; i < t.length; ++i){
        if(map.has(t[i])){
            map.set(t[i], map.get(t[i]) + 1);
        }else{
            map.set(t[i], 1);
        }
    }
    let distance = [...map.keys()].length;
    let left = 0;
    let right = 0;
    let minLeft = 0;
    let minRight = 0;
    let minLen = Infinity;
    while(left <= right && right < len){
        if(distance){
            if(map.has(s[right])){
                map.set(s[right], map.get(s[right]) - 1);
                if(map.get(s[right]) === 0){
                    distance-=1;
                }
                if(distance === 0){
                    if(right - left < minLen){
                        minLeft = left;
                        minRight = right;
                        minLen = right - left;
                    }
                    continue;
                }
            }
            right++;
        }else{
            if(map.has(s[left])){
                map.set(s[left], map.get(s[left]) + 1);
                if(map.get(s[left]) === 1){
                    if(right === len - 1){
                        if(right - left + 1 <= minLen){
                            minLeft = left;
                            minRight = right;
                            break;
                        }
                    }else{
                        distance += 1;
                        left++;
                        right++;
                        continue;
                    }
                }
            }
            left++;
            if(right - left <= minLen){
                minLeft = left;
                minLen = right - left;
            }
        }
    }
    if(minLen < len){
        return s.substring(minLeft, minRight + 1);
    }else{
        return "";
    }
};

const lengthOfLongestSubstring = function(s) {
    let len = s.length;
    if(len < 2){
        return len;
    }
    let map = new Map();
    let left = 0;
    let right = 0;
    let ans = 0;
    while(right < len){
        if(map.has(s[right]) && map.get(s[right]) > left){
            left = map.get(s[right]) + 1;
            map.set(s[right], right);
        }else{
            map.set(s[right], right);
            ans = Math.max(right - left + 1, ans);
        }
        right++;
    }
    return ans;
};

const findAnagrams = function(s, p) {
    let len = s.length;
    let map = new Map();
    for(let i = 0; i < p.length; ++i){
        map.set(p[i], map.has(p[i]) ? map.get(p[i]) + 1 : 1);
    }
    let distance = map.size;
    let left = 0;
    let right = 0;
    let res = [];
    while(right < len){
        if(map.has(s[right])){
            map.set(s[right], map.get(s[right]) - 1);
            if(map.get(s[right]) === 0){
                distance = distance - 1;
            }
        }
        while(distance === 0){
            if(map.has(s[left])){
                map.set(s[left], map.get(s[left]) + 1);
                if(map.get(s[left]) === 1){
                    distance= distance + 1;
                    res.push(left);
                }

            }
            left++;
        }
        right++;
    }
    return res;
};

const findMaxConsecutiveOnes = function(nums) {
    let len = nums.length;
    if(len < 2) return len;
    let map = new Map();
    map.set(1,0);
    let left = 0;
    let right = 0;
    let res = 0;
    let maxCount = 0;
    while(right < len){
        if(map.has(nums[right])){
            map.set(1, map.get(1) + 1);
            maxCount = Math.max(maxCount,map.get(1));
        }
        right++;
        if(right - left > maxCount + 1){
            if(map.has(nums[left])){
                map.set(1,map.get(1) - 1);
            }
            left++;
        }
        res = Math.max(res,right - left);
    }
    return res;
};

const countComponents = function(n, edges) {
    let visited = new Set();
    let ans = 0;
    for(let i = 0; i < edges.length; ++i){
        if(!visited.has(edges[i])){
            dfs(i, edges, visited);
            ans+=1;
        }
    }
    return ans;
};

const dfs = function(startIndex, edges, visited){
    if(!visited.has(edges[startIndex])){
        visited.add(edges[startIndex]);
        let item = edges[startIndex];
        dfs(item[1], edges, visited);
    }
    return;
}

console.log(countComponents(5,[[0,1],[1,2],[3,4]]));




